/* 
    归并排序
    O(NlogN)          O(N)
*/
let mergeSort = function (arr) {
    if (arr.length <= 1) {
        // console.log('data', arr);
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
};

function merge(leftArr, rightArr) {
    let resArr = [];
    while (leftArr.length > 0 && rightArr.length > 0) {
        resArr.push(leftArr[0] >= rightArr[0] ? rightArr.shift() : leftArr.shift());
    }
    if (leftArr.length > 0) {
        leftArr.forEach((element) => {
            resArr.push(element);
        });
    } else {
        rightArr.forEach((element) => {
            resArr.push(element);
        });
    }
    // console.log('merge', resArr);
    return resArr;
}

// let a = [1, 56, 5, 656, 32, 9, 2, 355, 565623, 5565, 56, 56, 56565, 5612, 545, 484];
// let res = mergeSort(a);
// console.log(1111111, res);
// console.log(res);

module.exports = {
    mergeSort
};
